159. Longest Substring with At Most Two Distinct Characters
Medium

Given a string s, return the length of the longest substring that contains at most two distinct characters.

 

Example 1:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

Example 2:

Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of English letters.
Accepted
149,355
Submissions
292,671
Seen this question in a real interview before?
Companies

Average Rating: 4.88 (60 votes)

Premium

Video Solution


 

Solution Article


Approach 1: Sliding Window

Intuition

To solve the problem in one pass let's use here sliding window approach with two set pointers left and right serving as the window boundaries.

The idea is to set both pointers in the position 0 and then move right pointer to the right while the window contains not more than two distinct characters. If at some point we've got 3 distinct characters, let's move left pointer to keep not more than 2 distinct characters in the window.

compute

Basically that's the algorithm : to move sliding window along the string, to keep not more than 2 distinct characters in the window, and to update max substring length at each step.

There is just one more question to reply - how to move the left pointer to keep only 2 distinct characters in the string?

Let's use for this purpose hashmap containing all characters in the sliding window as keys and their rightmost positions as values. At each moment, this hashmap could contain not more than 3 elements.

compute

For example, using this hashmap one knows that the rightmost position of character e in "eeeeeeeet" window is 8 and so one has to move left pointer in the position 8 + 1 = 9 to exclude the character e from the sliding window.

Do we have here the best possible time complexity? Yes, we do - it's the only one pass along the string with N characters and the time complexity is O(N)\mathcal{O}(N).

Algorithm

Now one could write down the algortihm.

  • Return N if the string length N is smaller than 3.
  • Set both set pointers in the beginning of the string left = 0 and right = 0 and init max substring length max_len = 2.
  • While right pointer is less than N:
    • If hashmap contains less than 3 distinct characters, add the current character s[right] in the hashmap and move right pointer to the right.
    • If hashmap contains 3 distinct characters, remove the leftmost character from the hashmap and move the left pointer so that sliding window contains again 2 distinct characters only.
    • Update max_len.

Implementation

Current
1 / 29

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) where N is a number of characters in the input string.

  • Space complexity : O(1)\mathcal{O}(1) since additional space is used only for a hashmap with at most 3 elements.

Problem generalization

The same sliding window approach could be used to solve the generalized problem :

Longest Substring with At Most K Distinct Characters

Report Article Issue

Comments: 31
sanyam3's avatar
Read More

Why is this problem classified as hard?

45
Show 6 replies
Reply
Share
Report
nishadkumar's avatar
Read More

The video solution is really well articulated! Loved the approach and simplicity.

8
Reply
Share
Report
rahulkun's avatar
Read More

less branchy approach would be put str[right] unconditionally and shirking the windows by increment left while size>2 O(N) time and O(2) space for hashmap

int lengthOfLongestSubstringTwoDistinct(string str) {
        int ans=0; 
        unordered_map<char,int> count;
        int l=0, r=0, N=str.length();
        while (r<N) {
          count[str[r]]++;
          while (count.size()>2 && r>=l) {
            count[str[l]]--;      
            if (count[str[l]]==0)
                count.erase(str[l]);
            l++;
          }  
          ans=max(ans,r-l+1);  
          r++;
        }
        return ans;
    }

7
Show 1 reply
Reply
Share
Report
kc786's avatar
Read More

I found this statement confusing "delete the leftmost character". Its actually not considering the left most character in the sliding window but in hash map(after sorting based on last seen index of the character). For example "eceba" is the given input. If we just consider the first character inserted in hash map then actually 'e' will be removed when encounter more than 2 distinct characters in string. But in fact we remove 'c' from hash map.

5
Show 1 reply
Reply
Share
Report
james_wo's avatar
Read More

How does finding the minimum value in a hashmap take less than linear time?

2
Show 2 replies
Reply
Share
Report
saurabhchris1's avatar
Read More

Python Time O(n) and Space O(1) no hashmap

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        last_char = ''
        second_last_char = ''
        last_char_count = 0
        maximum = 0
        currentMax = 0
        
        for char in s:
            if char == last_char or char == second_last_char:
                currentMax +=1
            else:
                currentMax = last_char_count + 1
                
            if char == last_char:
                last_char_count += 1
            else:
                last_char_count = 1
                second_last_char = last_char
                last_char = char
                
            maximum = max(currentMax, maximum)
                
        return maximum

3
Show 1 reply
Reply
Share
Report
khotiaintseva's avatar
Read More

Why does the python solution use defaultdict instead of a regular dict?

1
Show 1 reply
Reply
Share
Report
cjim8889's avatar
Read More

i know which company uses this question , lol

-1
Show 2 replies
Reply
Share
Report
aliabd11's avatar
Read More

Isn't determining the length of the hashmap, O(n)? So the time complexity of this solution would not be O(n).

0
Show 3 replies
Reply
Share
Report
user3662's avatar
Read More

using only one array solution:

public static int kUnique(String str, int k){
        k=2; // remove k=2 for k unique characters
        int start=0, maxlength=0, uniquecount=0;
        int[] hash = new int[256];
        Arrays.fill(hash, 0);
        for (int i =0; i< str.length(); i++){

            if (uniquecount < k){
                if (hash[str.charAt(i)] == 0) {
                    hash[str.charAt(i)]++;
                    uniquecount++;
                }
                else {
                    hash[str.charAt(i)]++;
                }
            }
            else{
                if (hash[str.charAt(i)]>0){
                    hash[str.charAt(i)]++;
                }
                else {
                    while (uniquecount >= k){
                        hash[str.charAt(start)]--;
                        if (hash[str.charAt(start)]==0){
                            uniquecount--;
                        }
                        start++;
                    }
                    if (hash[str.charAt(i)]==0){
                        hash[str.charAt(i)]++;
                        uniquecount++;
                    }
                }

            }
            maxlength = Math.max(maxlength, i - start +1);
        }
        if (uniquecount<k){
            return -1;
        }
        return maxlength;
    }

0
Show 2 replies
Reply
Share
Report
Success
Details
Runtime: 8 ms, faster than 74.82% of C++ online submissions for Longest Substring with At Most Two Distinct Characters.
Memory Usage: 7.8 MB, less than 63.19% of C++ online submissions for Longest Substring with At Most Two Distinct Characters.
Time Submitted
Status
Runtime
Memory
Language
06/17/2021 08:46Accepted8 ms7.8 MBcpp
05/25/2021 08:57Accepted12 ms7.9 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.